
def neighbours(maze: list[str], coord: tuple[int]) -> list[tuple[int]]:
    row = coord[0]
    col = coord[1]
    cell = maze[row][col]
    if cell == '>':
        return [(row, col + 1)]
    if cell == '<':
        return [(row, col - 1)]
    if cell == '^':
        return [(row - 1, col)]
    if cell == 'v':
        return [(row + 1, col)]

def dfs(maze: list[str], coord: tuple[int]) -> list[tuple[int]]:
    def do_dfs(target: tuple[int], count: int, visited: set, queue: list) -> list:
        if len(queue) == 0:
            return []

        res1 = do_dfs(target, count, visited, queue[1:])

        q = queue[0]
        if q == target:
            return [count] + res1
        
        visited.add(q)
        
        res2 = do_dfs(
            target, 
            count + 1, 
            visited,
            list(filter(lambda coord: coord not in visited, neighbours(maze, q)))
        )

        return res1 + res2

    return do_dfs(0, set(), [coord])
